\documentclass[a4paper,12pt]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage[top=2cm, bottom=2cm,left=2cm,right=2cm]{geometry}
\usepackage{graphicx}


\begin{document}
\begin{center}
\includegraphics[scale=0.7]{enseirb_matmeca.jpg}
\end{center}
\vspace{2cm}
\noindent\rule{\textwidth}{1mm}
\begin{center}
\Large
\textbf{Projet Compilation}
\end{center}
\normalsize
\noindent\rule{\textwidth}{1mm}

\large
\vspace{3cm}
\begin{center}

  \textit{Equipe :}
\\ Adèle VILLIERMET
\\ Vincent POMIER



\vspace{3cm}


\end{center}
\normalsize
\newpage
\tableofcontents
\newpage

\section{Introduction}

Le but de ce projet est de réaliser un compilateur d'un langage objet proche du language Ruby.
Le compilateur vérifiera les types, et générera la représentation intermédiaire pour un compilateur LLVM sous forme de fichier texte.
L'appel au compilateur LLVM permettra ainsi de finir la compilation en binaire et de générer du code.

\section{Table des symboles}

Le langage Rubic considéré dans ce projet utilise différents types de variables.
La première étape a été pour nous de choisir une représentation de ces types en C pour pouvoir les manipuler par la suite.\\

Les variables peuvent manipuler des booléens, des entiers, des doubles, des chaines de caractères et des objets. Nous avons donc choisi une représentation à l'aide de structures et de listes chaînées.

\vspace{0.5cm}
\begin{verbatim}
struct variable
{
  char* nom_var;
  int numvar;
  struct type* tvar;
  struct variable* suivant;
};
\end{verbatim}
\vspace{0.5cm}


\texttt{nom\_var} et \texttt{numvar} permettent l'identification des variables. Le numéro est fixé de manière unique par le compilateur et correspond à l'identifiant utilisé lors de la génération de code.

Le champ tvar est un pointeur sur une structure type.

\vspace{0.5cm}
\begin{verbatim}
struct type
{
  enum nom_type ntype;
  struct fct* class_fcts;
  struct params* fct_params;
  union{
    int vali;
    int valb;
    char* valst;
    double vald;
  };
};
\end{verbatim}
\vspace{0.5cm}

Celle-ci permet de connaitre le contenu de la variable.\\
Le champ ntype correspond à un enum qui indique le type : boolean, int, float, class, function ou éventuellement undef.\\

Les classes sont décrites par les fonctions qu'elles définissent, les noms de celles-ci sont stocké dans le champ \texttt{class\_fcts}.
Comme une classe peut-être définie en plusieurs fois, il est possible que le compilateur ait à ajouter une fonction à une classe déjà existante. C'est pourquoi nous avons choisis une structure de liste chaînée pour ce champ.

De même, les fonctions sont caractérisées par les types de leurs
paramètres et par leur type de retour. Ces informations sont stockées dans le champ \texttt{fct\_params} de la forme suivante:

\vspace{0.5cm}
\begin{verbatim}
struct params
{
  struct arg* arg1;
  enum nom_type retour;
};
\end{verbatim}
\vspace{0.5cm}

Nous avons choisi d'utiliser également une liste chainée pour les arguments afin de pouvoir les ajouter à la variable au fur et à mesure que le parseur les rencontre.

Enfin l'union permet de stocker la valeur de la variable lorsqu'il s'agit d'un autre type.

Selon le type de la variable, certains champs peuvent être inutile. Ils sont alors initialisés à NULL.\\

Ces choix de représentation ne nous ont pas tous été utiles puisque nous n'avont pas mis en oeuvre la totalité du compilateur attendu mais nous avons essayé d'anticiper au maximum les besoins que nous aurions pu rencontrer dans les étapes suivantes du projet.

Nous avons ensuite choisi d'ajouter à cette structure principale un pointeur sur une autre variable afin de pouvoir mettre en place une liste chainée qui sera notre table des symboles.
Pour utiliser celle-ci, nous avons mis en place des fonctions pour ajouter une variable à la table, une fonction a une classe et un argument à une fonction, mais également pour obtenir le type d'une variable donnée et libérer la table des symboles lorsqu'elle n'est plus utile.

%n'a pas sa place dans la table des symboles d'après moi irait ds traitement de fct que ns n'avons pas fait

%Ruby est un langage à typage dynamique: les types ne sont calculés qu'à l'exécution du code. Dans Rubic, les types seront calculés statiquement. Cela conduit à générer plusieurs versions de méthodes en général
%Pour réaliser le polymorphisme de cette méthode, on aura besoin de générer 2 codes de fonctions, l'un lorsque le paramètre est un objet de type A et l'autre quand a est de type B.
%Une méthode simple pour réaliser ceci est d'envisager une méthode poly pour chaque type possible du paramètre a: int, float, string, A, B et C (si seulement trois classes ont été créees). Puis la vérification des types est faite pour le code de la méthode pour chacun des types de paramètres: les erreur de type qu'on va trouver dans la méthode pour certaines valeurs de type du paramètre ne vont pas provoquer des erreurs de compilation, mais simplement permettre d'écarter ce typage de paramètre. 
%Au final, on a trouvé que la fonction a du polymorphisme, et les types possibles de poly sont int poly(A) ou string poly(B). Ces deux versions donneront lieu à deux implementations différentes, par exemple poly\_A et poly\_B. A chaque appel de la méthode poly, le typage devra déterminer quelle fonction en réalité il faut appeler.
%Cette approche, bien que couteuse, peut être envisagée quelque soit le nombre de paramètres de la fonction polymorphique. 
%numero unique pour chaque fct, changement du nom qd cree plusieurs fonctions pour polymorphisme ex poly\_A et poly\_B ici



\section{Actions sémantiques}

Une fois notre table des symboles implémentée, il nous a fallut ajouter les actions sémantiques à la grammaire dans le fichier \texttt{parse.y}. Dans un premier temps nous avons corrigé une erreur dans le fichier fourni: dans la règle \texttt{topstmt} on a rajouté \texttt{opt\_terms} avant le mot clef \texttt{END}.
Malheuresement par manque de temps et suite à de nombreuses difficultés de compréhension qui nous ont retardé, nous n'avons pas pu implémenté toutes les fonctionnalités proposées par le sujet. Nous nous sommes concentrés sur les déclarations de variables, les types et les opérations arithmétiques. 

\subsection{Types primaires}

La reconnaissance des types primaires constitue la base du compilateur. Nous avons utilisé la table des symboles décrite précédement pour les reconnaître et stocker les variables. Le type étant représenté par une structure dans notre projet, à chaque reconnaissance d'une nouvelle variable de type primaire il faut donc lui associé le type correspondant. Ensuite il faut donner un nom unique à cette nouvelle variable et la stocker dans la table des symboles. L'unicité du nom se fait grâce à un simple compteur qui s'incrémente à chaque nouvel ajout. Par exemple la reconnaissance d'un entier correspond à cette action sémantique:

\vspace{0.5cm}
\begin{verbatim}
primary : INT    {printf("int\n");
struct type ty; 
ty.ntype=3;
ty.vali=$1;
ty.class_fcts=NULL;
ty.fct_params=NULL;
char num[100];
sprintf(num,"%d",cmpt_val);
char name[256];strcat(name,"name_v");
strcat(name,num);
$$=ajouter_var(&t,&ty,name);
fprintf(f,"%%%d = add i32 %d,%d\n",
$$->numvar,$1,0);}

\end{verbatim}
\vspace{0.5cm}

En théorie le compilateur doit pouvoir gérer les nombres signés.

\subsection{Identificateurs}

Les identificateurs sont des chaines de caractères et posent la difficulté supplémentaire de pouvoir être soit de type primaire, soit un nom de fonction, soit une classe. Il faut donc dans un premier temps vérifier si l'identificateur appartient ou non à la table des symboles. Si c'est le cas alors on utilise l'identificateur reconnu (variable,classe ou fonction) sinon il est ajouté à la table. Basiquement l'action sémantique correspondant à un identificateur est la suivante:


\vspace{0.5cm}
\begin{verbatim}
lhs : ID {printf("id\n");
struct variable* w=t;
struct variable* v=chercher($1,w);
if(v==NULL){struct type ty; 
ty.ntype=6;
ty.class_fcts=NULL;
ty.fct_params=NULL;
$$=ajouter_var(&t,&ty,$1);
cmpt_val++;}
else{$$=v;}}

\end{verbatim}
\vspace{0.5cm}

Par défaut le code LLVM généré indique que les variables sont toutes locales. Il faudrait pouvoir gérer également les variables globales.

%%Ajouter code définitif premier lhs

\subsection{Opérations artihmétiques}

Pour ces fonctionnalités il faut faire très attention aux types des opérandes. En effet suivant si les variables sont de type entier ou flottant le code LLVM devant être généré n'est pas le même. Il faut donc traiter chacun des cas. Si les deux opérandes sont de type entier, on utilisera l'opération avec des valeurs entière, sinon si au moins une des opérandes est flottante on utilisera l'opération avec des valeurs flottantes.  

Par exemple voici l'action sémantique correspondant à l'addition de deux variables (2 représente le type float et 3 le type entier):



\vspace{0.5cm}
\begin{verbatim}
additive_expr : additive_expr '+' multiplicative_expr 
{printf("add\n");
if($1->tvar->ntype==2 && $3->tvar->ntype==2){struct type ty;
ty.ntype=2;
ty.vald=$1->tvar->vald+$3->tvar->vald;
ty.class_fcts=NULL;
ty.fct_params=NULL;
char num[100];
sprintf(num,"%d",cmpt_val);
char name[256];
strcat(name,"name_v");
strcat(name,num);
$$=ajouter_var(&t,&ty,name);
fprintf(f,"%%%d = fadd float %%%d,%%%d\n",$$->numvar,$1->numvar,$3->numvar);} 
else if($1->tvar->ntype==2 && $3->tvar->ntype==3)...
\end{verbatim}
\vspace{0.5cm}


%%Ajouter code addition définitif

\section{Génération de code}

La génération de code se fait par le biais des actions sémantiques. Il faut en effet, si nécessaire, écrire dans un fichier \texttt{.ll} le code assembleur LLVM de l'action décrite par la grammaire. Pour cela on a décidé d'ouvrir un fichier nommé \texttt{test.ll} dans lequel sera écrit le code LLVM au fur et à mesure que le code rubic sera parsé. Une fois le code écrit, le fichier est refermé et peut être compilé en code assembleur natif avec la commande \texttt{llc} et enfin le fichier \texttt{.s} obtenue peut être compilé. Malheureusement, le code LLVM renvoie plusieurs erreurs dont nous n'avons pas réussi à comprendre les causes.

\section{Conclusion}

En conclusion ce projet nous a permis de voir plus en détails la réalistation d'un compilateur bien que nous soyons conscients que ce que nous avons réalisé est loin du travail attendu. De gros problèmes de compréhension nous on ralenti et à plusieurs reprises nous avons du revoir notre implémentation et ainsi recommencer le projet du début. Nous regrettons notament de ne pas avoir pu traiter l'aspect objet du langage Rubic.



\end{document}
%grammaire ne gère pas les nombre négatif ni les new
